import java.math.BigDecimal
import java.util

import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import scala.util.Try

object Solution {



  def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val res = new Array[Int](2)
    val map = scala.collection.mutable.HashMap.empty[Int, Int]
    for (i <- 0 until nums.size) {
      if (map.contains(nums(i))) {
        res(1) = i
        res(0) = map.get(nums(i)).get
        return res
      } else {
        map.put(target - nums(i), i)
      }
    }
    res
  }

  class ListNode(var _x: Int = 0) {
    var next: ListNode = null
    var x: Int = _x
  }

  def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
    if (null == l1) return l2
    if (null == l2) return l1
    val dummyHead = new ListNode(0)
    var p = l1
    var q = l2
    var curr = dummyHead
    var carry = 0
    while (p != null || q != null) {
      val x = if (p != null) p._x else 0
      val y = if (q != null) q._x else 0
      val sum = carry + x + y
      carry = sum / 10
      curr.next = new ListNode(sum % 10)
      curr = curr.next
      if (p != null) p = p.next
      if (q != null) q = q.next
    }
    if (carry > 0) curr.next = new ListNode(carry)

    dummyHead.next
  }


  def lengthOfLongestSubstring(s: String): Int = {

    var res = 0
    var left = 0
    var right = 0
    val t = new mutable.HashSet[Character]()
    while (right < s.length)
      if (!t.contains(s.charAt(right))) {
        t.add(s.charAt({
          right += 1;
          right - 1
        }))
        res = Math.max(res, t.size)
      } else
        t.remove(s.charAt({
          left += 1;
          left - 1
        }))
    res
  }


  def findMedianSortedArrays(nums1: Array[Int], nums2: Array[Int]): Double = {
    val arr = nums1.union(nums2).sortWith(_.compareTo(_) < 0)
    if (arr.length % 2 == 0)
      (arr(arr.length / 2) + arr(arr.length / 2 - 1)) / 2.0
    else
      arr(arr.length / 2)

  }


  def longestPalindrome(s: String): String = {
    if (s.length == 1) return s
    var maxSize = 0
    //    var left = 0
    //    var right = 0
    var result = ""
    //    val t = new scala.collection.mutable.HashSet[Character]()
    for (i <- 0 until s.length; j <- 1 until s.length) {
      if (s(i).equals(s(j))) {
        if (j - i > maxSize) {
          maxSize = j - i
          result = s.substring(i, j + 1)
        }
      }
    }
    result
  }


  def reverse(x: Int): Int = {
    val len = Math.abs(x).toString.length
    var res = 0L
    var y = x
    for (i <- 0 until len) {
      val k: Int = y / Math.pow(10, len - i - 1).toInt
      if (k * Math.pow(10, i) > Integer.MAX_VALUE || k * Math.pow(10, i) < Integer.MIN_VALUE) return 0
      res += k * Math.pow(10, i).toInt
      y = y - k * Math.pow(10, len - i - 1).toInt
    }
    return if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) 0 else res.toInt
  }


  def isPalindrome(x: Int): Boolean = {
    if (x < 0) return false
    var len = 1
    while (x / len > 0) {
      len *= 10
    }
    var y = x
    while (y > 0) {
      val first = y / len
      val last = y % 10
      if (first != last) return false
      y = (y % len) / 10
      len = len / 100
    }
    true

  }

  def isMatch(text: String, pattern: String): Boolean = {
    if (pattern.isEmpty) return text.isEmpty
    val first_match = !(text.isEmpty) && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.')
    if (pattern.length >= 2 && pattern.charAt(1) == '*') isMatch(text, pattern.substring(2)) || (first_match && isMatch(text.substring(1), pattern))
    else first_match && isMatch(text.substring(1), pattern.substring(1))
  }

  def maxArea(height: Array[Int]): Int = {
    var left = 0
    var right = height.length
    var area = 0
    while (left < right) {
      if (height(left) >= height(right)) {
        area = Math.max(area, (right - left) * (height(left) - height(right)))
        right -= 1
      } else {
        area = Math.max(area, (right - left) * (height(right) - height(left)))
        left += 1
      }
    }
    area
  }

  def intToRoman(num: Int): String = {
    var num2 = num
    val symbol = Array("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
    val value = Array(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
    val str = new StringBuilder
    for (i <- 0 until symbol.size) {
      while (num2 >= value(i)) {
        str.append(symbol(i))
        num2 -= value(i)
      }
    }

    str.toString
  }

  def romanToInt(s: String): Int = {
    //val symbol=Array("M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I")
    //val value= Array(1000,900,500,400, 100, 90,  50, 40,  10, 9,   5,  4,   1)
    val map = Map('M' -> 1000, 'D' -> 500, 'C' -> 100, 'L' -> 50, 'X' -> 10, 'V' -> 5, 'I' -> 1)
    //    val map:Map[Char,Int] = Map('a'-> 1000)
    //var i=0
    var res = 0
    for (i <- s.length until 0) {
      val m = map(s.charAt(i))
      val n = map(s.charAt(i - 1))
      if (m > n) res += m else res -= m
    }
    res
  }


  def longestCommonPrefix(strs: Array[String]): String = {
    var i = 0
    var str = ""
    while (i < strs.length) {
      var flag = true
      var j = 1
      val sub = strs(0).substring(0, i)
      while (flag && j < strs.length) {
        if (strs(j).startsWith(sub)) j += 1 else flag = false
      }
      if (flag) str = sub
      i += 1
    }
    str

  }


  def generateParenthesis(n: Int): List[String] = {
    val list = scala.collection.mutable.ArrayBuffer.empty[String]
    generate(n, n, "", list)
    return list.toList
  }

  def generate(l: Int, r: Int, one: String, list: ArrayBuffer[String]): Unit = {
    if (l < 0 || r < 0 || l > r) return
    if (l == 0 && r == 0) {
      list += one
      return
    }
    generate(l - 1, r, one + "(", list)
    generate(l, r - 1, one + ")", list)

  }

  def helper(left: Int, right: Int, out: String, res: ArrayBuffer[String]): Unit = {
    if (left < 0 || right < 0 || left > right) return
    if (left == 0 && right == 0) {
      res += out
      return
    }
    helper(left - 1, right, out + "(", res)
    helper(left, right - 1, out + ")", res)
  }

  def mergeTwoLists(l1: ListNode, l2: ListNode): ListNode = {
    if (l1 == null) return l2
    else if (l2 == null) return l1
    if (l1.x < l2.x) {
      l1.next = mergeTwoLists(l1.next, l2)
      l1
    } else {
      l2.next = mergeTwoLists(l1, l2.next);
      l2
    }

  }

  def mergeKLists(lists: Array[ListNode]): ListNode = {
    if (lists.isEmpty) return null
    if (lists.length == 1) return lists(0)
    val length = lists.length
    val middle = (length - 1) / 2
    val l1 = mergeKLists(lists.take(middle + 1))
    val l2 = mergeKLists(lists.takeRight(length - middle - 1))
    return mergeTwoLists(l1, l2)
  }


  def swapPairs(head: ListNode): ListNode = {
    if (head == null) return null
    val zero = new ListNode(0)
    zero.next = head
    var pre = zero
    var cur = head
    while (cur != null && null != cur.next) {
      val next = cur.next.next
      cur.next.next = cur
      pre.next = cur.next
      if (next != null && next.next != null)
        cur.next = next.next
      else
        cur.next = next

      pre = cur
      cur = next


    }

    zero.next

  }


  def divide(dividend: Int, divisor: Int): Int = {
    if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE
    if (divisor == Integer.MIN_VALUE) return 0
    val sign = if ((dividend < 0) ^ (divisor < 0)) -1 else 1
    var m = if (dividend == Integer.MIN_VALUE) 2147483648L else Math.abs(dividend).toLong
    val n = Math.abs(divisor).toLong
    var res = 0
    if (n == 1) return if (sign == 1) m.toInt else -m.toInt
    while (m >= n) {
      var t = n
      var p = 1
      while (m >= (t << 1)) {
        t <<= 1
        p <<= 1
      }
      res += p
      m -= t
    }
    return if (sign == 1) res else -res
  }

  def reverseKGroup(head: ListNode, k: Int): ListNode = {
    if (head == null || k == 1) return head
    val zero = new ListNode(0)
    zero.next = head
    var pre = zero
    var cur = head
    var i = 0
    while (cur != null) {
      i += 1
      if (i % k == 0) {
        pre = reverseOneGroup(pre, cur.next)
        cur = pre.next
      } else {
        cur = cur.next
      }
    }
    zero.next
  }

  def reverseOneGroup(pre: ListNode, next: ListNode): ListNode = {
    val last = pre.next
    var cur = last.next
    while (cur != next) {
      last.next = cur.next
      cur.next = pre.next
      pre.next = cur
      cur = last.next
    }
    last
  }

  def findSubstring(s: String, words: Array[String]): List[Int] = {
    val arr = scala.collection.mutable.ArrayBuffer.empty[Int]
    if (s.isEmpty) return arr.toList
    val len = words(0).length
    val map = scala.collection.mutable.Map.empty[String, Int]
    for (i <- 0 until words.length) {
      if (map.contains(words(i))) {
        map += words(i) -> (map(words(i)) + 1)
      } else {
        map += words(i) -> 1
      }
    }
    val m = s.length - words.length * len
    for (j <- 0 until m) {
      var init = j
      var str = s.substring(j, j + len)
      var cnt = 0
      while (map.contains(str) && map(str) > 0 && init + len <= s.length) {
        map.put(str, map(str) - 1)
        cnt += 1
        init += len
        if (init + len <= s.length) {
          str = s.substring(init, init + len)
        }
      }
      if (cnt == words.length) arr += j
      if (cnt > 0) {
        map.clear()
        for (k <- 0 until words.length) {
          if (map.contains(words(k))) {
            map += words(k) -> (map(words(k)) + 1)
          } else {
            map += words(k) -> 1
          }
        }
      }
    }
    arr.toList
  }

  def findSubstring2(s: String, words: Array[String]): List[Int] = {
    val arr = scala.collection.mutable.ArrayBuffer.empty[Int]
    if (s.isEmpty) return arr.toList
    val len = words(0).length

    val m = s.length - words.length * len
    for (j <- 0 to m) {
      val str = s.substring(j, j + words.length * len)
      var i = 0
      val arrs = words.toBuffer
      while (i < words.length) {
        val sub = str.substring(i * len, (i + 1) * len)
        if (arrs.contains(sub)) {
          arrs -= sub
          i += 1
        } else i = Integer.MAX_VALUE
      }
      if (arrs.isEmpty) {
        arr += j
      }
    }
    arr.toList
  }

  def nextPermutation(nums: Array[Int]): Unit = {
    var i = nums.length - 1
    while (i > 0) {
      if (nums(i) > nums(i - 1)) {
        //找到第一个比它大的值
        var m = nums.length - 1
        var n = i - 1
        while (m > n) {
          if (nums(m) > nums(n)) {
            n = Integer.MAX_VALUE
          } else m -= 1
        }
        //交换顺序
        val temp = nums(m)
        nums(m) = nums(i - 1)
        nums(i - 1) = temp
        //reverse
        var l = i
        var r = nums.length - 1
        while (l < r) {
          val tem = nums(l)
          nums(l) = nums(r)
          nums(r) = tem
          l += 1
          r -= 1
        }
        return
      }
      i = i - 1
    }
  }


  def longestValidParentheses(s: String): Int = {
    val stack = new scala.collection.mutable.Stack[Int]
    var max = 0
    stack.push(-1)
    for (i <- 0 until s.length) {
      if (s.charAt(i) == '(') {
        stack.push(i)
      } else {
        stack.pop()
        if (stack.nonEmpty) {
          max = Math.max(max, i - stack.head)
        } else {
          stack.push(i)
        }
      }
    }
    max
  }


  def searchRange(nums: Array[Int], target: Int): Array[Int] = {

    var l = 0
    var r = nums.length - 1
    var left = -1
    var right = -1

    while (l <= r) {
      val mid = (l + r) / 2
      if (nums(mid) < target) {
        l += 1
      } else if (nums(mid) > target) {
        r -= 1
      } else {
        //if (nums.length == 1) return Array(0,0)
        var mi = mid
        while (mi >= 0) {
          if(mi ==0) left = 0
          else if (nums(mi) > nums(mi - 1)) {
            left = mi
            mi = -1
          } else mi -= 1

        }
        var m = mid
        while (m <= nums.length - 1) {
          if(m == nums.length - 1) right = m
          else if (nums(m) < nums(m + 1)) {
            right = m
            m = Integer.MAX_VALUE
          } else m += 1
        }
        r = -1
      }

    }
    Array(left, right)
  }

  def searchInsert(nums: Array[Int], target: Int): Int = {
    var l = 0
    var r = nums.length - 1

    while(l <= r ){
      var mid = (l+r)/2
      if(nums(mid) == target) return mid
      if(nums(mid) > target){
        var m =mid-1
        while(m>=0){
          if(nums(m) < target ){
            return m+1
            }else if(nums(m) == target){
          return m
          }else {
          m -=1
          if(m == -1) return 0
          }
          }

          l -=1
          }else{
          var n = mid+1
          while(n<=nums.length -1){
            if(nums(n) >=target ){
              return n
            }else{
              n +=1
              if(n == nums.length) return nums.length
            }
          }
          r +=1
          }
          }
          if(nums(0) < target) 1 else 0
            }



  def isValidSudoku(board: Array[Array[Char]]): Boolean = {
    val arr = new Array[Boolean](9)
    for(i <- 0 until 9){
      util.Arrays.fill(arr,false)
      for(j <- 0 until 9){
        val f = isChecked(arr,board(i)(j))
        if(!f) return false
      }
    }
    for(i <- 0 until 9){
      util.Arrays.fill(arr,false)
      for(j <- 0 until 9){
        val f = isChecked(arr,board(j)(i))
        if(!f) return false
      }
    }

    for(i <- 0 until 3){
      for(j <- 0 until 3) {
        util.Arrays.fill(arr, false)
        for (k <- 0 until 9) {
          val f = isChecked(arr, board(i*3 + k/3)(j*3 + k%3))
          if (!f) return false
        }
      }
    }
    true
  }


  def solveSudoku(board: Array[Array[Char]]): Unit = {

    solve(board)

  }

  private def solve(board: Array[Array[Char]]): Boolean = {
    for(i <- 0 until 9; j <- 0 until 9){
      if(board(i)(j) == '.'){
        for(k <- '1' to '9'){
          board(i)(j) = k
          if(isValid(board,i,j) && solve(board) ) return true
          board(i)(j) = '.'
        }
        return false
      }
    }
    true
  }


  private def isValid(board: Array[Array[Char]], row: Int, col: Int) : Boolean= {
    for(i <- 0 until 9){
      if(i!=col && board(row)(i) == board(row)(col))
        return false
    }
    for(i <- 0 until 9){
      if(i!=row && board(i)(col) == board(row)(col))
        return false
    }

    val x = 3*(row/3)
    val y = 3*(col/3)
    for(i <- x until x+3){
      for(j <- y until y+3) {
        if(i!=row && j!=col && board(i)(j) == board(row)(col))  return false
      }
    }
    true
  }


  private def isChecked(arr:Array[Boolean], c:Char): Boolean ={
    if(c == '.') return true
    val num = c - '0'
    if(num < 1 || num> 9 || arr(num-1) ) return false
    arr(num-1) = true
    true
  }








  def countAndSay(n: Int): String = {
    if(n == 1) return "1"
    val s = countAndSay(n-1)+"*"
    var i = 0
    var count = 1
    var sb = ""
    while(i < s.length-1){
      val c = s.charAt(i)
      val max = s.charAt(i+1)
      if(c == max){
        count += 1
      }else{
        sb = sb +count +c
        count = 1
      }
      i += 1
    }
    sb
  }



  def combinationSum(candidates: Array[Int], target: Int): List[List[Int]] = {
    val ans = scala.collection.mutable.ArrayBuffer.empty[List[Int]]
    val cans = candidates.sorted
    backTracking(scala.collection.mutable.ArrayBuffer.empty[Int],0,target,ans,cans)
    ans.toList
  }


  def backTracking(cur : ArrayBuffer[Int],from:Int,target:Int,ans:scala.collection.mutable.ArrayBuffer[List[Int]],cans:Array[Int]):Unit={
    if (target == 0) {
      ans += cur.toList
    } else {
      var i = from
      while (i < cans.length && cans(i) <= target) {
        cur += cans(i)
        backTracking(cur, i, target - cans(i),ans,cans)
        cur -= cans(i)
        i += 1
      }
    }
  }



  def firstMissingPositive(nums: Array[Int]): Int = {
    val arr = new  Array[Int](nums.length)
    for(i <- nums.indices){
      if(nums(i) > 0 && nums(i) <= nums.length){
        arr(nums(i)-1) = nums(i)
      }
    }
    for(i <- nums.indices){
      if(arr(i) ==0){
        return i+1
      }
    }
    arr.length+1
  }

  def jump(nums: Array[Int]): Int = {
    val pre = new Array[Int](nums.length)
    var reach = 0
    for(i <- nums.indices){
      if(i + nums(i) > reach){
        var j = reach +1
        while(j <= i + nums(i) && j < nums.length){
          pre(j) = i
          j+=1
        }
        reach = i + nums(i)
      }
    }
    var ans = 0
    var k = nums.length -1
    while(k >0){
      k = pre(k)
      ans +=1
    }
    ans
  }


  import java.util



  def permute(nums: Array[Int]): List[List[Int]] = {
    val res =  scala.collection.mutable.ArrayBuffer.empty[List[Int]]
    val len = nums.length
    if (len == 0 || nums == null) return res.toList
    // 采用前后元素交换的办法，dfs解题
    exchange(nums, 0, len, res)
    res.toList
  }

  def exchange(nums: Array[Int], i: Int, len: Int, res:scala.collection.mutable.ArrayBuffer[List[Int]]): Unit = { // 将当前数组加到结果集中
    if (i == len - 1) {
      val list = scala.collection.mutable.ArrayBuffer.empty[Int]
      var j = 0
      while (j < len) {
        list += nums(j)
        j += 1
      }
      res += list.toList
      return
    }
    // 将当前位置的数跟后面的数交换，并搜索解
    var j = i
    while (j < len) {
      swap(nums, i, j)
      exchange(nums, i + 1, len,res)
      swap(nums, i, j)
      j += 1
    }
  }

  def swap(nums: Array[Int], i: Int, j: Int): Unit = {
    val temp = nums(i)
    nums(i) = nums(j)
    nums(j) = temp
  }



  def main(args: Array[String]): Unit = {
    //    val nums = Array(2, 7, 11, 15)
    //    val target = 9
    //    twoSum(nums, target).foreach(println(_))
    //
    val l1 = new ListNode(1)
    l1.next = new ListNode(2)
    l1.next.next = new ListNode(3)
    l1.next.next.next = new ListNode(4)
    l1.next.next.next.next = new ListNode(5)


    var a = 8
    a <<= 1
    var m = reverseKGroup(l1, 2)

    val d = 100.001.toString

    val arr= Array(1)

    //    val arr = Array(1, 2, 3)
    println(firstMissingPositive(arr))
  }
}
